This invention relates to a parallel type multiplying circuit for multiplying binary numbers of a plurality of bits with each other.
In general, the product of binary numbers is found by finding a partial product of a multiplicand in each digit and a multiplier in each digit and adding the respective partial products together. FIG. 1 shows a conventional parallel type multiplying circuit for realizing this algorithm. Suppose that a multiplicand X and multiplier Y are 4-bit numbers. In this case 16 (=4.times.4) unit circuits U.sub.1 to U.sub.16 are connected in an array and each has the same configuration. For brevity's sake, only the unit circuit U.sub.16 is illustrated in detail in FIG. 1 and the other unit circuits are shown in a block form. Each unit circuit comprises an AND circuit 10 for finding a partial product A of a multiplicand X.sub.i and multiplier Y.sub.j and a full adder 12 for adding the partial product A to an ouput B from a preceding stage with a carry input C' in order to find a sum output S and carry output C.
Unit circuits U.sub.1 to U.sub.4 find respective partial products of multiplicands X.sub.1 to X.sub.4 and multiplier Y.sub.1 of a first (a least significant) bit. Unit circuits U.sub.5 to U.sub.8 find partial products of the multiplicands X.sub.1 to X.sub.4 and multiplier Y.sub.2 of a second bit. Unit circuits U.sub.9 to U.sub.12 find partial products of the multiplicands X.sub.1 to X.sub.4 and multiplier Y.sub.3 of a third bit. Unit circuits U.sub.13 to U.sub.16 find partial products of the multiplicands X.sub.1 to X.sub.4 and multiplier Y.sub.4 in a fourth (a most significant) bit. The sum outputs S of the unit circuits U.sub.1, U.sub.5, U.sub.9, U.sub.13, U.sub.14, U.sub.15 and U.sub.16 and a carry output C of the unit circuit U.sub.16 correspond to products P.sub.1, . . . and P.sub.8 of the first (the least significant) bit to the eighth (the most significant) bit, respectively.
Such a conventional multiplying circuit can find all the partial products, and it is necessary to provide (the bit number of the multiplicand).times.(the bit number of the multiplier) unit circuits. Where the number of the multiplicand (which is usually the same as the number of multiplier) is small, for example, 4 or 8, no appreciable problem occurs as to the number of the unit circuits required. However, since the unit circuits increase in proportion to the square of the bit number of the multiplicand (or multiplier), a plurality of hardware elements are required for an increase in the bit number of the multiplicand (or multiplier). For example, 576 unit circuits are required to multiply 24-bit numbers with each other. Where the unit circuits are made up of MOS elements, about 15,000 MOSFETs are necessary. This applies not only to a parallel multiplying circuit utilizing a simple algorithm, but also to a parallel multiplying circuit utilizing a Booth or a Wallace algorithm.
A product obtained by finding all the partial products as mentioned above is very accurate. However, the number of significant digits of a product (2n bits) of two binary numbers of n bits are only up to n and it is sufficient if an accuracy of upper n bits is maintained with respect to the product.